package 牛客.树;
/*
 * @Author   helen
 * @Date     2021/4/14 15:57
 * @Descriptions
 * 请根据二叉树的前序遍历，中序遍历恢复二叉树，并打印出二叉树的右视图
    示例1
        输入  [1,2,4,5,3],[4,2,5,1,3]
        返回值  [1,3,5]
 */
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class 给出先序和后序打印树的右视图 {
    public BTreeNode<Integer> reBuild(int[] pre, int[] in){
        if(pre == null || pre.length == 0)
            return null;
        BTreeNode<Integer> root = new BTreeNode<>(pre[0]);
        int flag = 0;
        for (int i = 0; i < in.length; i++) {
            if(pre[0] == in[i]){
                flag = i;
                break;
            }
        }
        root.left = reBuild(Arrays.copyOfRange(pre, 1, flag+1), Arrays.copyOfRange(in, 0, flag));
        root.right = reBuild(Arrays.copyOfRange(pre, flag+1, pre.length), Arrays.copyOfRange(in, flag+1, in.length));
        return root;
    }

    public int[] solve (int[] pre, int[] in) {
        // write code here
        if(pre == null || pre.length ==0)
            return null;
        //重建二叉树
        BTreeNode<Integer> root = reBuild(pre, in);
        //按层序遍历二叉树的方法找到每层的最右边的数的结点，并add进list里面，然后转换成整型数组
        Queue<BTreeNode<Integer>> queue = new LinkedList<>();
        ArrayList<Integer> list = new ArrayList<>();
        int count = 0;       //计数器，用于记录出队列的元素个数，以便判断是否为该层的最右结点
        int nextCount = 1;   //该层的结点数
        queue.add(root);
        while (!queue.isEmpty()){
            BTreeNode<Integer> node = queue.poll();
            count++;
            if(node.left != null){
                queue.add(node.left);
            }
            if(node.right!= null){
                queue.add(node.right);
            }
            if(count == nextCount){
                count = 0;
                nextCount = queue.size();
                list.add(node.data);
            }
        }
        int[] arr = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            arr[i] = list.get(i);
        }
        return arr;
    }

    public static void main(String[] args) {
        给出先序和后序打印树的右视图 obj = new 给出先序和后序打印树的右视图();
        int[] pre = {1,2,4,5,3};
        int[] in = {4,2,5,1,3};
        int[] solve = obj.solve(pre, in);
        for (Integer i: solve) {
            System.out.println(i);
        }
    }
}
